/** 将 nums 分成 k 个相邻的非空子数组，求每个子数组的平均值的最大总和
 * 如[9,1,2,3,9]的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var largestSumOfAverages = function (nums, k) {
    // 计算前缀和  sum[i]表示前i个元素的和
    const sum = Array(nums.length + 10).fill(0)
    for (let i = 1; i <= nums.length; i++) {
        sum[i] = sum[i - 1] + nums[i - 1]
    }

    // dp[i][j]表示前i个元素划分为j个子集的最大平均值
    const dp = Array(nums.length + 10).fill(0).map(v => Array(k + 10).fill(0))

    for (let i = 1; i <= nums.length; i++) {
        // 前i个元素最多划分为i个子集，同时也要满足小于题目限制的k个子集
        for (let j = 1; j <= Math.min(i, k); j++) {
            // 只划分为一个子集时直接用 前缀和 除以 数量
            if (j == 1) {
                dp[i][j] = sum[i] / i
            } else {
                // 此处i、j已经固定且j>=2 枚举最后一个子数组的起点（最后一个子数组的范围是 可变起点 到 第i个元素）
                for (let kk = 2; kk <= i; kk++) {
                    dp[i][j] = Math.max(dp[i][j], dp[kk - 1][j - 1] + ((sum[i] - sum[kk - 1]) / (i - kk + 1)))
                }
            }
        }
    }

    return dp[nums.length][k]
};